#
# @lc app=leetcode.cn id=72 lang=python3
#
# [72] 编辑距离
#


# @lc code=start
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        len1 = len(word1)
        len2 = len(word2)
        matrix = [[0] * (len2 + 1) for _ in range(len1 + 1)]
        matrix[0] = list(range(len2 + 1))

        def f(x):
            x[1][0] = x[0]

        list(map(f, enumerate(matrix)))

        for i in range(len1):
            for j in range(len2):
                left = matrix[i][j + 1] + 1
                right = matrix[i + 1][j] + 1
                middle = matrix[i][j]
                if word1[i] != word2[j]:
                    middle += 1
                matrix[i + 1][j + 1] = min(left, right, middle)

        return matrix[len1][len2]


# @lc code=end
